/**
 * @author LKQ
 * @date 2022/2/23 13:00
 * @description
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.validPalindrome("abca");
    }
    public boolean validPalindrome(String s) {
        int n = s.length(), left = 0, right = n - 1;
        while (s.charAt(left) == s.charAt(right) && left < right) {
            left++;
            right--;
        }
        if (left == right) {
            return true;
        }
        // 遇到不相等的两个字符，1，删除left, 看 s[left + 1, right]是否回文 2，删除right, 看 s[left, right-1]是否回文
        return isPalindrome(s, left + 1, right) || isPalindrome(s, left, right - 1);
    }
    public boolean isPalindrome(String s, int start, int end) {
        while (start < end) {
            if (s.charAt(start) != s.charAt(end)) {
                return false;
            }
            start++;
            end--;
        }
        return true;
    }
}
